package com.leaves.leetcode.array.t1534_CountGoodTriplets;

import java.util.*;


/**
 * 核心要点：
 * 部分固定 + 绝对值交集范围 + 频次前缀数组(前缀和，小于等于当前下标得数出现次数)
 * 有序下标 + 中间遍历 + 绝对值交集范围 + 双指针0开始确定范围数字个数
**/
 class Solution {

    /**
     * 有序下标 + 中间遍历 + 双指针0开始确定范围数字个数
     * 这个是O(n^2)，因为最后k2和k1的遍历不会超过2n，但通过将下标数组根据原数组元素从小到大排序，得到有序的下标数组，
     * 通过在下标数组中遍历中间数下标j，可以得到两个有序的i、k原数值数组。有序！所以可以简单通过双指针达到统计范围数字出现的次数
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(T)
     * @param arr a b c
     * @return
     */
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int ans = 0;
        int n = arr.length;
        Integer[] idxArr = new Integer[n];
        Arrays.setAll(idxArr, e -> e);
        Arrays.sort(idxArr, (e1, e2) -> arr[e1] - arr[e2]);

        for (int j : idxArr) {
            int vj = arr[j];
            List<Integer> leftArr = new ArrayList<>();
            for (int i : idxArr) {
                if (i < j && Math.abs(arr[i] - vj) <= a) leftArr.add(arr[i]);
            }

            List<Integer> rightArr = new ArrayList<>();
            for (int k : idxArr) {
                if (j < k && Math.abs(vj - arr[k]) <= b) rightArr.add(arr[k]);
            }

            // leftArr和rightArr是有序的，在固定了leftArr的元素和确定rightArr元素的范围后，可以通过双指针的方式实现确定符合要求的数的个数
            int k1 = 0, k2 = 0;
            for (int x : leftArr) {
                while (k1 < rightArr.size() && rightArr.get(k1) < x - c) k1++;
                while (k2 < rightArr.size() && rightArr.get(k2) <= x + c) k2++;
                ans += k2 - k1;
            }
        }

        return ans;
    }

    /**
     * 部分固定 + 绝对值交集范围 + 频次前缀数组(前缀和，小于等于当前下标得数出现次数)
     * 1、注意边界情况
     * 时间复杂度：O(n*(n + T))
     * 空间复杂度：O(T)
     * @param nums
     * @return
     */
    public int countGoodTriplets_official(int[] arr, int a, int b, int c) {
        int res = 0;
        int n = arr.length;
        int mx = Integer.MIN_VALUE;
        for(int num : arr) mx = Math.max(num, mx);
        int[] sum = new int[mx + 1];
        for (int i = arr[0]; i <= mx; i++) sum[i]++;
        for (int j = 1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                if (Math.abs(arr[j] - arr[k]) <= b) {
                    int l = Math.max(Math.max(arr[j] - a, arr[k] - c), 0);
                    int r = Math.min(Math.min(arr[j] + a, arr[k] + c), mx);
                    if (l == 0) res += sum[r];
                    else if (l <= r) res += sum[r] - sum[l-1];
                }
            }
            for (int i = arr[j]; i <= mx; i++) sum[i]++;
        }

        return res;
    }



    /**
     * 暴力解法
     * 时间复杂度：O(n^3)
     * 空间复杂度：O(1)
     * @param arr a b c
     * @return
     */
    public int countGoodTriplets_violence(int[] arr, int a, int b, int c) {
        int n = arr.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                        res++;
                    }
                }
            }
        }

        return res;
    }
 }